package sliding_window

//995.给定一个二进制数组 nums 和一个整数 k 。
//k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。
//
//返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回-1。
//子数组 是数组的 连续 部分。
//
//示例 1：
//输入：nums = [0,1,0], K = 1
//输出：2
//解释：先翻转 A[0]，然后翻转 A[2]。

//示例 2：
//输入：nums = [1,1,0], K = 2
//输出：-1
//解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

//示例 3：
//输入：nums = [0,0,0,1,0,1,1,0], K = 3
//输出：3
//解释：
//翻转 A[0],A[1],A[2]:A变成 [1,1,1,1,0,1,1,0]
//翻转 A[4],A[5],A[6]:A变成 [1,1,1,1,1,0,0,0]
//翻转 A[5],A[6],A[7]:A变成 [1,1,1,1,1,1,1,1]

//查分数组
//由于对同一个子数组执行两次翻转操作不会改变该子数组，所以对每个长度为 kk 的子数组，应至多执行一次翻转操作。
//对于若干个 k 位翻转操作，改变先后顺序并不影响最终翻转的结果。不妨从 nums[0] 开始考虑，若 nums[0]=0，则必定要翻转从位置 0 开始的子数组.
//若 nums[0]=1，则不翻转从位置 0 开始的子数组。
//按照这一策略，我们从左到右地执行这些翻转操作。由于翻转操作是唯一的，若最终数组元素均为 1，则执行的翻转次数就是最小的。
//用 n 表示数组 nums 的长度。若直接模拟上述过程，复杂度将会是O(nk) 的。如何优化呢？

//考虑不去翻转数字，而是统计每个数字需要翻转的次数。对于一次翻转操作，相当于把子数组中所有数字的翻转次数加 1。
//这启发我们用差分数组的思想来计算当前数字需要翻转的次数。
//我们可以维护一个【差分数组】 diff，其中 diff[i] 表示两个相邻元素 nums[i−1] 和 nums[i] 的翻转次数的差，对于区间[l,r]，将其元素全部加 1，只会影响到 l 和 r+1 处的差分值， 故 diff[l] 增加 1，diff[r+1] 减少 1。
//通过累加差分数组可以得到【当前位置需要翻转的次数】，我们用变量 revCnt 来表示这一累加值。
//遍历到 nums[i] 时，若nums[i]+revCnt 是偶数，则说明当前元素的实际值为 0，需要翻转区间 [i,i+k−1]，
//我们可以直接将 revCnt 累加值 增加 1，diff[i+k] 减少 1。
//注意到若i+k>n 则无法执行翻转操作，此时应返回 −1
func minKBitFlips(nums []int, k int) (ans int) {
	n := len(nums)
	diff := make([]int, n+1) //反转次数的查分数组
	revCnt := 0              //当前位置需要反转的次数，累加值
	for i, v := range nums {
		//revCnt += diff[i]
		//模2意义下的加减法与异或等价
		revCnt ^= diff[i]
		//if (v+revCnt)%2 == 0 { //是偶数,说明当前元素的实际值为0
		if v^revCnt == 0 {
			if i+k > n {
				return -1
			}
			ans++
			//revCnt++    //反转累加值
			revCnt ^= 1
			//diff[i+k]-- //减少反转次数的差值
			diff[i+k] ^= 1
		}
	}
	return
}

//滑动窗口
//能否将空间复杂度优化至 O(1) 呢？
//回顾方法一的代码，当遍历到位置 i 时，若能知道位置 i−k 上发生了翻转操作，便可以直接修改revCnt，从而去掉 diff 数组。
//注意到 0≤nums[i]≤1，我们可以用 nums[i] 范围之外的数来表达「是否翻转过」的含义。
//具体来说，若要翻转从位置 i 开始的子数组，可以将nums[i] 加 2，这样当遍历到位置 i'时，若有 [i'-k]>1则说明在位置 i'-k 上发生了翻转操作。
func minKBitFlipsSW(nums []int, k int) (ans int) {
	n := len(nums)
	revCnt := 0 //当前位置需要反转的次数，累加值
	for i, v := range nums {

		if i >= k && nums[i-k] > 1 {
			revCnt ^= 1
			nums[i-k] -= 2 //复原数组元素，若允许修改数组nums，则可以省略
		}

		if v^revCnt == 0 {
			if i+k > n {
				return -1
			}
			ans++
			//revCnt++    //反转累加值
			revCnt ^= 1
			nums[i] += 2
		}
	}
	return
}

//利用队列模拟滑动窗口
//位置 i 现在的状态，和它被前面 K−1 个元素翻转的次数（奇偶性）有关。
//我们使用队列模拟滑动窗口，该滑动窗口的含义是前面 K−1 个元素中，以哪些位置起始的 子区间 进行了翻转。
//该滑动窗口从左向右滑动，如果当前位置 i 需要翻转，则把该位置存储到队列中。
//遍历到新位置j(j<i+K) 时，队列中元素的个数代表了 i 被前面 K−1 个元素翻转的次数。
//
//当 A[i] 为 0，如果 i 位置被翻转了偶数次，那么翻转后仍是 0，当前元素需要翻转；
//当 A[i] 为 1，如果 i 位置被翻转了奇数次，那么翻转后变成 0，当前元素需要翻转。
//综合上面两点，我们得到一个结论，如果 len(que) % 2 == A[i] 时，当前元素需要翻转。
//
//当 i+K>N 时，说明需要翻转大小为 K 的子区间，但是后面剩余的元素不到 K 个了，所以返回 -1。
func minKBitFlipsQueue(nums []int, k int) (ans int) {
	count, n := 0, len(nums)
	queue := make([]int, 0)
	for i := 0; i < n; i++ {

		//shrink queue
		if len(queue) > 0 && i >= queue[0]+k { //i >= que[0]+k 弹出队列头部元素
			queue = queue[1:]
		}
		rCount := len(queue)

		//1.本来是1，翻转奇数次变为0，所以需要再次翻转，放入队列
		//2.本来是0，翻转偶数次还是0，所以需要再次翻转，放入队列
		if rCount%2 == nums[i] {
			if i > n-k {
				return -1
			}
			count++
			queue = append(queue, i)
		}
	}
	return count
}
